package practice1_100;

import java.util.ArrayList;
import java.util.List;

public class Practice54 {
    /**
     * 拿到这题的时候，本来思路不是很清晰，
     * 我们首先联想一下就是一个环一个环的遍历，从外向里。关键问题就是控制上下遍历长度，左右遍历的长度一致,类似于下图，我才用的是
     * ======
     * =    =
     * =    =
     * ======
     * @param matrix
     * @return
     */
    public List<Integer> solution(int[][] matrix){
        //最外环的终止的行列，这里减去1，是为了在转弯的过程中好计算
        int row=matrix.length-1,column=matrix[0].length-1;
        //最外环的开始的行列
        int columnStart=0,rowStart=0;
        //list记录结果数据的总长度
        int len=(column+1)*(row+1);
        //int[] count =new int[(column+1)*(row+1)];
        List<Integer> list =new ArrayList<>();
        //当前元素下表，保证index<len(结果数据的总长度)
        int index =0;
        while (column>=columnStart&&row>=rowStart){//保证环的 起始处 小于等于 终止处
            //横向 从左往右
            for (int i = columnStart; i <column&&index<len ; i++) {
                list.add(matrix[rowStart][i]);
                index++;
            }
            //纵向 从上往下
            for (int j = rowStart; j < row&&index<len; j++) {
                list.add(matrix[j][column]);
                index++;
            }
            //横向 从右向左
            for (int i=column;i>columnStart&&index<len;i--){
                list.add(matrix[row][i]);
                index++;
            }
            //纵向 从下往上
            for (int j = row; j >rowStart&&index<len; j--) {
                list.add(matrix[j][columnStart]);
                index++;
            }
            column--;
            row--;
            rowStart++;
            columnStart++;
        }
        //最终写出的代码有个小bug，在中心对称的正方形矩阵中，中心元素不能被添加到最后，所以再次加一个判断
        if(matrix.length==matrix[0].length&&matrix.length%2==1) list.add(matrix[matrix.length/2][matrix.length/2]) ;
        return list;
    }

    public static void main(String[] args) {
        List<Integer> list =new Practice54().solution(new int[][]{{1,2,3,4,21},{5,6,7,8,22},{9,10,11,12,23},{13,14,15,16,24},{17,18,19,20,25}});
//        {1,2,3,4,21},{5,6,7,8,22},{9,10,11,12,23},{13,14,15,16,24},{17,18,19,20,25}
        System.out.println(list);
    }
}
